package com.demo416_分割等和子集;

import java.util.Arrays;

/**
 * 把一个数组分为和相等的2个子集
 *
 * 这个和把一个数组分成k个相等的子集是一样的做法:
 *
 * 那就是取2个桶, 每个桶的容量 刚好是这个所有元素和的一半.
 *
 * 分别遍历所有的元素, 看看是不是刚好可以放下所有的元素, 如果可以则是true,  否则是false
 *
 * 超时了!!!!!
 */
public class Solution {
    public boolean canPartition(int[] nums) {
        // 排序
        Arrays.sort(nums);
        // 求和
        int sum = Arrays.stream(nums).sum();
        // 求均值
        int average=sum/2;
        // 特判1
        if (sum%2!=0){
            return false;
        }
        // 特判2
        if (nums[nums.length-1]>average){
            return false;
        }
        // 创建2个桶
        int[] buckets = new int[2];
        Arrays.fill(buckets,average);

        // 递归
        boolean result = dfs(nums,buckets,0);

        //
        return result;

    }

    private boolean dfs(int[] nums, int[] buckets, int startIndex) {
        // 边界条件: 如果数组元素都放进去了
        if (startIndex==nums.length){
            return true;
        }

        // 横向遍历 + 递归: 横向遍历桶: 纵向遍历元素 ~
        for (int i = 0; i < 2; i++) {
            // 剪枝
            if (i>0&&buckets[i]==buckets[i-1]){
                continue;
            }
            // 尝试把当前元素放进桶里
            if (buckets[i]>=nums[startIndex]){
                buckets[i]-=nums[startIndex];
                // 递归
                boolean result = dfs(nums, buckets, startIndex + 1);
                if (result){ //每次都递归成功了, 那么就返回true
                    return true;
                }
                // 回溯
                buckets[i]+=nums[startIndex];

            }
        }

        return false;
    }
}
